class Node {
    constructor() {
        this._parentNode = undefined;
        this._preNode = undefined;
        this._nextNode = undefined;
        this._firstChildNode = undefined;
    }
    get parentNode() {return this._parentNode;}
    get preNode() {return this._preNode;}
    get nextNode() {return this._nextNode;}
    get firstChildNode() {return this._firstChildNode;}
    get lastChildNode() {
        let _node = this._firstChildNode;
        while(_node) {
            if(_node._nextNode) {
                _node = _node._nextNode;
            } else break;
        }
        return _node;
    }
    get depth() {
        let _depth = 0;
        let _node = this._parentNode;
        while(_node) {
            ++_depth;
            _node = _node._parentNode;
        }
        return _depth;
    }
    get childrenCount() {
        let _ret = 0;
        let _node = this._firstChildNode;
        while(_node) {
            ++_ret;
            _node = _node._nextNode;
        }
        return _ret;
    }
    get isLeaf() {return this._firstChildNode ? false : true;}
}

function _InsertAIntoB(aNode, bNode, offset) {
    const N = bNode.childrenCount;
    if(N <= 0) {
        _InsertAAsFirstChild(aNode, bNode);
    } else if(offset >= N) {
        let _node = bNode.lastChildNode;
        _InsertAAfterB(aNode, _node);
    } else {
        let _node = _GetChildNode(bNode, offset);
        _InsertABeforeB(aNode, _node);
    }
}
function _InsertAAsFirstChild(aNode, bNode) {
    aNode._parentNode = aNode._nextNode = aNode._preNode = undefined;
    let _node = bNode._firstChildNode;
    bNode._firstChildNode = aNode;
    aNode._parentNode = bNode;
    if(_node) {
        _node._preNode = aNode;
        aNode._nextNode = _node;
    }
}
function _InsertABeforeB(aNode, bNode) {
    aNode._parentNode = aNode._nextNode = aNode._preNode = undefined;
    if(bNode._parentNode._firstChildNode == bNode) {
        bNode._parentNode._firstChildNode = aNode;
    }
    let _oldPreNode = bNode._preNode;
    bNode._preNode = aNode;
    aNode._parentNode = bNode._parentNode;
    aNode._preNode = _oldPreNode;
    aNode._nextNode = bNode;
    if(_oldPreNode) {
        _oldPreNode._nextNode = aNode;
    }
}
function _InsertAAfterB(aNode, bNode) {
    aNode._parentNode = aNode._nextNode = aNode._preNode = undefined;
    let _oldNextNode = bNode._nextNode;
    bNode._nextNode = aNode;
    aNode._parentNode = bNode._parentNode;
    aNode._preNode = bNode;
    aNode._nextNode = _oldNextNode;
    if(_oldNextNode) {
        _oldNextNode._preNode = aNode;
    }
}
function _Remove(node) {
    let _oldParentNode = node._parentNode;
    let _oldPreNode = node._preNode;
    let _oldNextNode = node._nextNode;
    node._parentNode = undefined;
    node._preNode = undefined;
    node._nextNode = undefined;
    if(_oldPreNode) {
        _oldPreNode._nextNode = _oldNextNode;
    }
    if(_oldNextNode) {
        _oldNextNode._preNode = _oldPreNode;
    }
    if(_oldParentNode) {
        if(_oldParentNode._firstChildNode == node) {
            _oldParentNode._firstChildNode = _oldNextNode;
        }
    }
}
function _RemoveChildNode(node, offset) {
    let _cNode = _GetChildNode(node, offset);
    if(_cNode) {
        _Remove(_cNode);
        return _cNode;
    }
    return undefined;
}
function _RemoveAllChildren(node) {
    let _ret = node._firstChildNode;
    let _node = _ret;
    while(_node) {
        _node._parentNode = undefined;
        _node = _node._nextNode;
    }
    node._firstChildNode = undefined;
    return _ret;
}
function _MoveAIntoB(aNode, bNode, offset) {
    _Remove(aNode);
    _InsertAIntoB(aNode, bNode, offset);
}
function _MoveABeforeB(aNode, bNode) {
    _Remove(aNode);
    _InsertABeforeB(aNode, bNode);
}
function _MoveAAfterB(aNode, bNode) {
    _Remove(aNode);
    _InsertAAfterB(aNode, bNode);
}
function _GetChildNode(node, offset) {
    let _ret = node._firstChildNode;
    while(--offset >= 0 && _ret) {
        if(!_ret._nextNode) return _ret;
        _ret = _ret._nextNode;
    }
    return _ret;
}

/**
 * 设计原则：
 * 1）任何一个节点（Node），在同一时刻，要么存在于树（Unique Tree）上，称为附着状态（attached）；要么不存在于树上，成为游离态（detached）；
 * 2）存在于树上的节点，在同一时刻，只能出现在一个位置；
 * 3）不存在父节点，亦不存在任何兄弟节点；
 * 4）无父节点的节点，其深度为0，子孙节点按照层级关系以此递增；
 * 5）树不会维护处于游离态节点之间的关系；
 */
class UniqueTree {
    constructor(key, rootNode) {
        Object.defineProperty(this, 'key', {value: key, writable: false, enumerable: true, configurable: false});
        this._rootNode = rootNode;
        this._mapNode = new Map();
        this._StoreNodeToMap(rootNode);
    }
    _StoreNodeToMap(node) {
        this._mapNode.set(node[this.key], node);
    }

    InsertAIntoB(aNode, bNode, offset) {
        if(this.IsAttached(aNode) || this.IsDetached(bNode)) return false;
        this._StoreNodeToMap(aNode);
        _InsertAIntoB(aNode, bNode, offset);
        return true;
    }
    InsertABeforeB(aNode, bNode) {
        if(this.IsAttached(aNode) || this.IsDetached(bNode)) return false;
        this._StoreNodeToMap(aNode);
        _InsertABeforeB(aNode, bNode);
        return true;
    }
    InsertAAfterB(aNode, bNode) {
        if(this.IsAttached(aNode) || this.IsDetached(bNode)) return false;
        this._StoreNodeToMap(aNode);
        _InsertAAfterB(aNode, bNode);
        return true;
    }
    RemoveNodeByKey(key) {
        let _node = this._mapNode.get(key);
        if(!_node) return undefined;
        this._mapNode.delete(key);
        _Remove(_node);
        return _node;
    }
    RemoveNode(node) {
        if(this.IsDetached(node)) return false;
        this._mapNode.delete(node[this.key]);
        _Remove(node);
        return true;
    }
    RemoveChildNode(node, offset) {
        if(this.IsDetached(node)) return undefined;
        return _RemoveChildNode(node, offset);
    }
    RemoveAllChildren(node) {
        if(this.IsDetached(node)) return undefined;
        return _RemoveAllChildren(node);
    }
    MoveAIntoB(aNode, bNode, offset) {
        if(this.IsDetached(aNode) || this.IsDetached(bNode)) return false;
        _MoveAIntoB(aNode, bNode, offset);
        return true;
    }
    MoveABeforeB(aNode, bNode) {
        if(this.IsDetached(aNode) || this.IsDetached(bNode)) return false;
        _MoveABeforeB(aNode, bNode);
        return true;
    }
    MoveAAfterB(aNode, bNode) {
        if(this.IsDetached(aNode) || this.IsDetached(bNode)) return false;
        _MoveAAfterB(aNode, bNode);
        return true;
    }
    GetNodeByKey(key) {return this._mapNode.get(key);}
    GetChildNodeByOffset(node, offset) {
        if(this.IsDetached(node)) return false;
        return _GetChildNode(node, offset);
    }
    IsAttached(node) {return this._mapNode.has(node[this.key]);}
    IsDetached(node) {return !this.IsAttached(node);}
    TraverseDescendant(dockNode, node) {
        if(this.IsDetached(dockNode)) return undefined;
        if(node) {
            if(this.IsDetached(node)) return undefined;
            if(node._firstChildNode) {
                return node._firstChildNode;
            } else if(node._nextNode) {
                return node._nextNode;
            } else {
                let _tmp = node._parentNode;
                while(_tmp && _tmp != dockNode) {
                    if(_tmp._nextNode) {
                        return _tmp._nextNode;
                    }
                    _tmp = _tmp._parentNode;
                }
                return undefined;
            }
        } else {
            return dockNode._firstChildNode;
        }
    }
    DebugPrint(msg) {
        const _KEY = this.key;
        let _arr = [this._rootNode];
        let _node = this.TraverseDescendant(this._rootNode);
        while(_node) {
            _arr.push(_node);
            _node = this.TraverseDescendant(this._rootNode, _node);
        }
        let _currentDepth = 0;
        console.groupCollapsed(msg);
        for(let i = 0, N = _arr.length; i < N; ++i) {
            _node = _arr[i];
            if(_node.isLeaf) {
                if(_node.depth < _currentDepth) {
                    console.groupEnd();
                    _currentDepth = _node.depth;
                } else if(_node.depth > _currentDepth) {
                    _currentDepth = _node.depth;
                }
                console.log(_node[_KEY]);
            } else {
                if(_node.depth < _currentDepth) {
                    console.groupEnd();
                    _currentDepth = _node.depth;
                } else if(_node.depth > _currentDepth) {
                    _currentDepth = _node.depth;
                }
                console.group(_node[_KEY]);
            }
        }
        while(--_currentDepth >= 0) {
            console.groupEnd();
        }
        console.groupEnd();
        console.log('map:', this._mapNode);
    }
}

module.exports = Object.freeze({
    Node,
    UniqueTree,
});
